#include <stdio.h>
#include <stdlib.h>
//线性表之双向链表
typedef int ElemType;
typedef struct node
{
    ElemType data;
    struct node *prev;
    struct node *next;
}Node;
Node *Initlist()
{
    Node *s=(Node *)malloc(sizeof(Node));
    s->data=0;
    s->prev=NULL;
    s->next=NULL;
}
//头插法
void addhead(Node *ps,ElemType n)
{
    Node *p=(Node *)malloc(sizeof(Node));
    p->data=n;
    p->prev=ps;
    p->next=ps->next;
    ps->next=p;
    if(p->next!=NULL)
    {
        p->next->prev=p;
    }
}
//尾插法
void addtail(Node *ps,ElemType n)
{
    Node *p=(Node *)malloc(sizeof(Node));
    p->data=n;
    //遍历找到尾节点
    Node *q=ps;
    while(q->next)
    {
        q=q->next;
    }
    q->next=p;
    p->prev=q;
    p->next=NULL;
}
//打印
void printlist(Node *ps)
{
    Node *p=ps->next;  //从首元节点开始打印
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}
//删除
void deletelist(Node *ps,int n)
{
   //先遍历找到n-1节点
   Node *p=ps;
   int i;
   for(i=0;i<n-1;i++)
   {
    p=p->next;
   } //循环结束p指向第n-1节点
   Node *q=p->next; //q指向第n节点
   p->next=q->next;
   q->next->prev=p;
   free(q);
}
//释放链表
void freelist(Node *ps)
{
    Node *p=ps;
    Node *q;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
}
int main()
{
    Node *list=Initlist();
    //插入
    addhead(list,22);
    addhead(list,52);
    addtail(list,66);
    addtail(list,88);
    //打印
    printlist(list);
    //删除:删除第n个元素
    int n;
    scanf("%d",&n);
    deletelist(list,n);
    //打印
    printlist(list);
    //释放链表
    freelist(list);
    return 0;
}